


#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <unordered_map>
#include <algorithm>
using namespace std;

class Solution
{
public:
    vector<vector<string>> groupAnagrams1(vector<string>& strs)
    {
        vector<vector<string>> res;
        unordered_map<string, vector<string>> hash;

        for (const auto& e : strs)
        {
            string tmp(e);

            sort(tmp.begin(), tmp.end());
            hash[tmp].push_back(e);
        }

        for (const auto& [x, y] : hash)
        {
            res.push_back(y);
        }

        return res;
    }

    vector<vector<string>> groupAnagrams2(vector<string>& strs)
    {
        vector<vector<string>> res;
        unordered_map<string, vector<string>> hash;

        for (const auto& e : strs)
        {
            string tmp;
            int cnt[26] = { 0 };

            for (const auto& ch : e)
            {
                ++cnt[ch - 'a'];
            }
            for (const auto& val : cnt)
            {
                tmp += to_string(val);
                if (val > 9)
                    tmp += '#';
            }

            hash[tmp].push_back(e);
        }

        for (const auto& [x, y] : hash)
        {
            res.push_back(y);
        }

        return res;
    }

    bool evaluateTree(TreeNode* root)
    {
        if (!root->left && !root->right)
            return root->val;

        bool left = evaluateTree(root->left);
        bool right = evaluateTree(root->right);

        if (2 == root->val)
            return left | right;
        else
            return left & right;
    }

    int sumNumbers(TreeNode* root)
    {
        int res = 0;
        _sumNumbers(root, 0, res);

        return res;
    }

    TreeNode* pruneTree(TreeNode* root)
    {
        if (nullptr == root)
            return nullptr;

        root->left = pruneTree(root->left);
        root->right = pruneTree(root->right);
        if (!root->left && !root->right && !root->val)
            return nullptr;
        else
            return root;
    }

private:
    void _sumNumbers(TreeNode* root, int path, int& res)
    {
        if (!root)
            return;

        path = path * 10 + root->val;

        if (!root->left && !root->right)
        {
            res += path;
            return;
        }

        _sumNumbers(root->left, path, res);
        _sumNumbers(root->right, path, res);
    }
};

class AnimalShelf
{
public:
    AnimalShelf() {}

    void enqueue(vector<int> animal)
    {
        if (animal[1])
            _dog.push(animal[0]);
        else
            _cat.push(animal[0]);
    }

    vector<int> dequeueAny()
    {
        if (_cat.empty())
            return dequeueDog();
        else if (_dog.empty())
            return dequeueCat();
        else if (_cat.front() < _dog.front())
            return dequeueCat();
        else
            return dequeueDog();
    }

    vector<int> dequeueDog()
    {
        if (_dog.empty())
            return { -1, -1 };

        int dog = _dog.front();
        _dog.pop();
        return { dog, 1 };
    }

    vector<int> dequeueCat()
    {
        if (_cat.empty())
            return { -1, -1 };

        int cat = _cat.front();
        _cat.pop();
        return { cat, 0 };
    }
private:
    queue<int> _cat;
    queue<int> _dog;
};

#if 0
class AnimalShelf
{
public:
    AnimalShelf()
    {}

    void enqueue(vector<int> animal)
    {
        if (animal[1])
            _dog.push({ animal[0], _order++ });
        else
            _cat.push({ animal[0], _order++ });
    }

    vector<int> dequeueAny()
    {
        if (_cat.empty() && _dog.empty())
            return { -1, -1 };
        else if (_cat.size() && _dog.empty())
            return dequeueCat();
        else if (_cat.empty() && _dog.size())
            return dequeueDog();
        else
        {
            auto cat = _cat.front(), dog = _dog.front();
            if (cat.second < dog.second)
                return dequeueCat();
            else
                return dequeueDog();
        }
    }

    vector<int> dequeueDog()
    {
        if (_dog.empty())
            return { -1, -1 };

        auto dog = _dog.front();
        _dog.pop();

        return { dog.first, 1 };
    }

    vector<int> dequeueCat()
    {
        if (_cat.empty())
            return { -1, -1 };
        auto cat = _cat.front();
        _cat.pop();

        return { cat.first, 0 };
    }
private:
    int _order = 0;
    queue<pair<int, int>> _cat;
    queue<pair<int, int>> _dog;
};
#endif

void Test1()
{
    vector<string> vs = {"bdddddddddd","bbbbbbbbbbc"};

    Solution().groupAnagrams1(vs);
}

int main()
{
    Test1();

	return 0;
}